package offer;

/**
 * @Author Elephas
 * @Date 2022/1/29
 **/

@FunctionalInterface
public interface MinPathSum {
    /**
     * consider we have a m x n matrix grid, find the shortest path from grid[0][0] to grid[m-1][n-1]
     * @param grid
     * @return
     */
    int minPathSum(int[][] grid);
}
class MinPathSumImpl1 implements MinPathSum{
    /**
     * o(mn),o(mn)
     * let matrix path[i][j] represent the min cost from grid[0][0] to grid[i][j]
     * then we can get a equation
     * path[i][j] = min{path[i-1][j]+grid[i][j],path[i][j-1]+grid[i][j]} , i>0,j>0
     *            = path[i-1][j]+grid[i][j] , i>0,j=0
     *            = path[i][j-1]+grid[i][j] , i=0,j>0
     *            = 0 , i=0,j=0
     * @param grid
     * @return
     */
    @Override
    public int minPathSum(int[][] grid) {
        final int m = grid.length;
        final int n = grid[0].length;
        int[][] path = new int[m][n];
        path[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) {
            path[i][0] = path[i-1][0] + grid[i][0];
        }
        for (int j = 1; j < n; j++) {
            path[0][j] = path[0][j-1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                path[i][j] = Math.min(path[i-1][j]+grid[i][j],path[i][j-1]+grid[i][j]);
            }
        }
        return path[m-1][n-1];
    }
}

class MinPathSumImpl2 implements MinPathSum{
    /**
     * optimize  o(mn),o(n)
     * @param grid
     * @return
     */
    @Override
    public int minPathSum(int[][] grid) {
        final int m = grid.length;
        final int n = grid[0].length;
        int[] path = new int[n];
        path[0] = grid[0][0];
        for (int j = 1; j < n; j++) {
            path[j] = path[j-1] + grid[0][j];
        }
        for (int i = 1; i < m; i++) {
            path[0] = path[0] + grid[i][0];
            for (int j = 0; j < n; j++) {
                path[j] = Math.min(path[j]+grid[i][j],path[j-1]+grid[i][j]);
            }
        }
        return path[n-1];
    }
}